/*
 * @lc app=leetcode.cn id=72 lang=swift
 *
 * [72] 编辑距离
 */

// @lc code=start
class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let firstCharacters = Array(word1)
        let firstLength = firstCharacters.count
        let secondCharacters = Array(word2)
        let secondLength = secondCharacters.count
        
        guard firstLength != 0 else{
            return secondLength
        }
        guard secondLength != 0 else {
            return firstLength
        }
        
        var dp = [[Int]](repeating: [Int](repeating: 0, count: secondLength + 1), count: firstLength + 1)
        //当其中一个字符串为空时，需要改变的次数是另一个字符串的长度
        for i in 0 ... firstCharacters.count {
            dp[i][0] = i
        }
        for i in 0 ... secondCharacters.count{
            dp[0][i] = i
        }
        
        for i in 1...firstLength {
            for j in 1...secondLength {
                if firstCharacters[i-1] == secondCharacters[j-1] {
                    dp[i][j] = dp[i-1][j-1]
                }else{
                    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                }
            }
        }
        
        return dp[firstLength][secondLength]
    }
}

// @lc code=end

